#include <iostream>
#include <cstdlib>
#include <limits>

#define BLACK false
#define RED true
#define MIN (std::numeric_limits<T>::min())

template <typename T>
class Node
{
public:
	T data;
	Node<T>* lc;
	Node<T>* rc;
	Node<T>* parent;
    bool color = RED;
    Node(){parent = lc = rc = NULL;}
	Node(T _data);
    ~Node(){};
};

template <typename T>
class RedBlackTree
{
private:
    void inorder_walk(Node<T>* _x) const;   //BST
    void release(Node<T>* _x);   //delete one node
    Node<T>* tree_search(Node<T>* _x, T _data);   //zu jian
    void transplant(Node<T>* u, Node<T>* v);    
    void rightrotate(Node<T> *_x);
    void leftrotate(Node<T> *_x);
    
    void rbinsert(Node<T> *_z);   //RBT, using rbinsertfixup
    void rbinsertfixup(Node<T> *_z);    //RBT, for rbinsert
    void rbtransplant(Node<T>* u, Node<T>* v);   //RBT, for rbdel
    void rbdel(Node<T> *_z);   //RBT, using rbtransplant, rbdelfixup
    void rbdelfixup(Node<T> *x);   //RBT, for rbdel
    
    Node<T>* root;
    Node<T>* nil;
    
public:
    RedBlackTree();
    RedBlackTree(T _data);
    ~RedBlackTree();
	Node<T>* min(Node<T>* _x) const;
    Node<T>* max(Node<T>* _x) const;
    Node<T>* successor(Node<T>* _x) const;
    Node<T>* predecessor(Node<T>* _x) const;
    void inorder_walk() const;    //BST
    
    void insert(T _data);    //BST
    Node<T>* tree_search(T _data);
    void tree_delete(Node<T>* z);
    void rbinsert(T _data);   //RBT jie kou
    void rbdel(T _data);    //RBT jie kou
};

//Node-------------------------------------------------------- 
template <typename T>
Node<T>::Node(T _data)
{
    data = _data;
    parent = lc = rc = NULL;
};

//RedBlackTree-private----------------------------------------
template <typename T>
void RedBlackTree<T>::inorder_walk(Node<T>* _x) const
{
    if(_x != nil)
    {
		inorder_walk(_x->lc);
		std::cout << _x->data << "  ";
		inorder_walk(_x->rc);
    }
};

template <typename T>
void RedBlackTree<T>::release(Node<T>* _x)
{
    if(_x != nil)
    {
		release(_x->lc);
		release(_x->rc);
		delete _x;
    }	
};

template <typename T>
Node<T>* RedBlackTree<T>::tree_search(Node<T>* _x,T _data)
{
    if(_x == nil || _data == _x->data)
        return _x;
    if(_data < _x->data)
    	return tree_search(_x->lc,_data);
    else
    	return tree_search(_x->rc,_data);
};

template <typename T>
void RedBlackTree<T>::transplant(Node<T>* u, Node<T>* v)
{
    if(u->parent == nil)
    	root = v;
    else if(u == u->parent->lc)
    	u->parent->lc = v;
    else 
		u->parent->rc = v;
		
    if(v != nil)
    	v->parent = u->parent;
};

template <typename T>
void RedBlackTree<T>::rightrotate(Node<T>* _x)
{
    Node<T>* y = _x->lc;
    _x->lc = y->rc;
    if(y->rc != nil)
		y->rc->parent = _x;
    y->parent = _x->parent;
    if(_x->parent == nil)
		root = y;
    else if(_x == _x->parent->lc)
		_x->parent->lc = y;
    else
		_x->parent->rc = y;
    y->rc = _x;
    _x->parent = y;
};

template <typename T>
void RedBlackTree<T>::leftrotate(Node<T> *_x)
{
    Node<T>* y = _x->rc;
    _x->rc = y->lc;
    if(y->lc != nil)
		y->lc->parent = _x;
    y->parent = _x->parent;
    if(_x->parent == nil)
		root = y;
    else if(_x == _x->parent->lc)
		_x->parent->lc = y;
    else
		_x->parent->rc = y;
    y->lc = _x;
    _x->parent = y;
};

template <typename T>
void RedBlackTree<T>::rbinsert(Node<T> *_z)
{
    Node<T>* y;
    Node<T>* x;
    y = nil;
    x = root;
    while(x != nil)
    {
        y = x;
        if(_z->data < x->data)
      	    x = x->lc;
        else 
			x = x->rc;
    }
    _z->parent = y;
    if(y == nil)
    	root = _z;
    else if(_z->data < y->data)
    	y->lc = _z;
    else 
		y->rc = _z;
    _z->lc = nil;
    _z->rc = nil;
    _z->color = RED;
    rbinsertfixup(_z);
};

template <typename T>
void RedBlackTree<T>::rbinsertfixup(Node<T> *_z)
{
    while(_z->parent->color == RED)
    if(_z->parent == _z->parent->parent->lc)
	{
	    Node<T>* y = _z->parent->parent->rc;
	    if(y->color == RED)
	    {
			_z->parent->color = y->color = BLACK;
			_z->parent->parent->color = RED;
			_z = _z->parent->parent;
		if(_z->parent->color == BLACK)
		    break;
	    }
	    else
	    {
			if(_z == _z->parent->rc)
			{
        	    _z = _z->parent;
			    leftrotate(_z);
			}
        	_z->parent->color = BLACK;
        	_z->parent->parent->color = RED;
			rightrotate(_z->parent->parent);
	    }
	}
    else if(_z->parent == _z->parent->parent->rc)
	{
	    Node<T>* y = _z->parent->parent->lc;
	    if(y->color == RED)
	    {
			_z->parent->color = y->color = BLACK;
			_z->parent->parent->color = RED;
			_z = _z->parent->parent;
			if(_z->parent->color == BLACK)
			    break;
	    }
	    else
	    {
			if(_z == _z->parent->lc)
			{
                _z = _z->parent;
		   		rightrotate(_z);
			}
            _z->parent->color = BLACK;
            _z->parent->parent->color = RED;
			leftrotate(_z->parent->parent);
	    }
	}
    root->color = BLACK;
};

template <typename T>
void RedBlackTree<T>::rbtransplant(Node<T>* u, Node<T>* v)
{
    if(u->parent == nil)
        root = v;
    else if(u == u->parent->lc)
        u->parent->lc = v;
    else
		u->parent->rc = v;
    v->parent = u->parent;
};

template <typename T>
void RedBlackTree<T>::rbdel(Node<T> *_z)
{
    Node<T>* y = _z;
    bool original_color_y = y->color;
    Node<T>* x;
    if(_z->lc == nil)
    {
		x = _z->rc;
		rbtransplant(_z, _z->rc);
    }
    else if(_z->rc == nil)
    {
		x = _z->lc;
		rbtransplant(_z, _z->lc);
    }
    else
    {
    	y = min(_z->rc);
    	original_color_y = y->color;
    	x = y->rc;
		if(y->parent != _z)
    	{
    	    rbtransplant(y, y->rc);
    	    y->rc = _z->rc;
    	    y->rc->parent = y;
    	}
    	rbtransplant(_z, y);
    	y->lc = _z->lc;
    	y->lc->parent = y;
    	y->color = _z->color;
    }
    if(original_color_y == BLACK)
    	rbdelfixup(x);
};

template <typename T>
void RedBlackTree<T>::rbdelfixup(Node<T>* x)
{
    while (x != root && x->color == BLACK)
    	if(x == x->parent->lc)
    	{
    		Node<T>* w = x->parent->rc;
    		if(w->color == RED)
    		{
    		    w->color = BLACK;
    		    x->parent->color = RED;
    		    leftrotate(x->parent);
    		    w = x->parent->rc;
    		}
    		if(w->lc->color == BLACK && w->rc->color == BLACK)
    		{
    		    w->color = RED;
    		    x = x->parent;
    		}
    		else
			{
			    if(w->rc->color == BLACK)
		 	    {
					w->lc->color = BLACK;
					w->color = RED;
					rightrotate(w);
					w = x->parent->rc;
			    }
			    w->color = x->parent->color;
			    x->parent->color = BLACK;
			    w->rc->color = BLACK;
			    leftrotate(x->parent);
			    x = root;
			}
	    }
	    else
     	{
    		Node<T> *w = x->parent->lc;
    		if(w->color == RED)
    		{
    		    w->color = BLACK;
    		    x->parent->color = RED;
    		    rightrotate(x->parent);
    		    w = x->parent->lc;
    		}
    		if(w->rc->color == BLACK && w->lc->color == BLACK)
    		{
    		    w->color = RED;
    		    x = x->parent;
    		}
    		else
			{
			    if(w->lc->color == BLACK)
			    {
					w->rc->color = BLACK;
					w->color = RED;
					leftrotate(w);
					w = x->parent->lc;
			    }
		 	    w->color = x->parent->color;
			    x->parent->color = BLACK;
			    w->lc->color = BLACK;
			    rightrotate(x->parent);
			    x = root;
			}
        }
    x->color = BLACK;   
};

//RedBlackTree--public-----------------------------------------
template <typename T>
RedBlackTree<T>::RedBlackTree()
{
	nil = new Node<T>;
	nil->color = BLACK;
	nil->data = MIN;
	root = nil;
}

template <typename T>
RedBlackTree<T>::RedBlackTree(T _data)
{
    nil = new Node<T>;
    nil->color = BLACK;
    nil->data = MIN;
    Node<T>* r = new Node<T>;
    r->data = _data;
    r->lc = nil;
    r->rc = nil;
    r->parent = nil;
    root = r;
};

template <typename T>
RedBlackTree<T>::~RedBlackTree()
{
    release(root);
    delete nil;
};

template <typename T>
Node<T>* RedBlackTree<T>::min(Node<T>* _x) const
{
    while (_x->lc != nil)
    {
    	_x = _x->lc;
	}
    return _x;
};

template <typename T>
Node<T>* RedBlackTree<T>::max(Node<T>* _x) const
{
    while (_x->rc != nil)
	{
		_x = _x->rc;
	}
    return _x;
};

template <typename T>
Node<T>* RedBlackTree<T>::successor(Node<T>* _x) const
{
    Node<T>* x = _x;
    if(x->rc != nil)
		return min(x->rc);
    Node<T>* y = x->parent;
    while (y != nil && x == y->rc)
    {
		x = y;
		y = y->parent;
    }
    return y;
};

template <typename T>
Node<T>* RedBlackTree<T>::predecessor(Node<T>* _x) const
{
    Node<T>* x = _x;
    if(x->lc != nil)
    {
        return max(x->lc);
    }
	Node<T>* y = x->parent;
    while(y != nil && x == y->lc)
    {
        x = y;
        y = y->parent;
    }
    return y;
};

template <typename T>
void RedBlackTree<T>::inorder_walk() const
{
    inorder_walk(root);
    std::cout << std::endl;
};

template <typename T>
void RedBlackTree<T>::insert(T _data)
{
    Node<T>* y = nil;
    Node<T>* x = root;
    Node<T>* p = new Node<T>(_data);
    while (x != nil)
    {
		y = x;
		if(p->data  < x->data)
		    x = x->lc;
		else
		    x = x->rc;
    }
    p->parent = y;
    if(y == nil)
		root = p;
    else if(p->data < y->data)
		y->lc = p;
    else
		y->rc = p;
};

template <typename T>
Node<T>* RedBlackTree<T>::tree_search(T _data)
{
    tree_search(root,_data);
};

template <typename T>
void RedBlackTree<T>::tree_delete(Node<T>* z)
{
    if(z->lc == nil)
	    transplant(z, z->rc);
    else if(z->rc == nil)
	    tansplant(z, z->lc);
    else
    {
		Node<T>* y;
   		y = min(z->rc);
    	if(y->parent != z)
    	{
     	    transplant(y, y->rc);
    	    y->rc = z->rc;
    	    y->rc->parent = y;
    	}
    	transplant(z, y);
    	y->lc = z->lc;
    	y->lc->parent = y;
    }
};

template <typename T>
void RedBlackTree<T>::rbinsert(T _data)
{
    Node<T> *x = new Node<T>(_data);
    rbinsert(x);
};

template <typename T>
void RedBlackTree<T>::rbdel(T _data)
{
	rbdel(tree_search(_data));
}


